It is known in the prior art of speech signal compression techniques used in communication systems to apply vector quantization, based on the operation of a source coder for coding contiguous blocks of samples as a vector rather than as isolated samples based on scalar quantization. In vector quantization systems, each input vector is encoded with a binary codeword, selected by means of comparison with a set of stored reference vectors, known as codevectors or patterns, which form a codebook. A nearest neighbour pattern matching technique based on a search procedure is used to encode the input vector by the best matching pattern according to the pre-stored codebook.
Rate distortion theory guarantees a performance arbitrarily close to the optimum for waveform vector quantizers operating on vectors of sufficiently large dimension. However, this theoretical result has had little impact on the use of vector quantization in currently available coding systems. This is mainly due to the complexity of their real-time implementation, which exhibits exponential growth with the vector dimension at a given bit rate.
The complexity issues associated with the implementation of vector quantization are broadly discussed in two tutorial papers entitled "Vector quantization", R. M. Gray, IEEE ASSP Magazine, pp. 4-27, Apr. 1984 and "Vector Quantization: A Pattern-Matching Technique for Speech Coding", A. Gersho and V. Cuperman, IEEE Communications Magazine, 1983, pp. 15-21. As stated therein, the implementation complexity in signal processing hardware is related to two main factors: computational complexity and the memory capacity required for the quantization process.
With regard to the computational complexity problem, the main obstacle to using vector quantization for high dimensional vectors is based on the fact that a k-dimensional vector quantizer operating at a rate of r bits/sample, requires a number of computations per sample of the order of 2.sup.kr and a memory of k2.sup.kr words if a full search through the codebook is performed for each input vector.
In a full search procedure, also known as an exhaustive search procedure, each codevector in the codebook has to be tested to determine if it is the nearest codevector to the input vector. The criterion for the nearest codevector (or best match) is determined on the basis of the minimal distortion associated with representing the input vector by it nearest codevector.
The distortion measure is the minimum mean square error (MMSE) which is expressed by means of the Euclidean distance between the two vectors. Thus, a full search procedure is comprised of calculations for the distortion or the distance between the input vector and each of the codebook vectors. Performing the search in the original k-dimensional space of the sample process requires the search to consist of the whole space, which is the main difficulty.
Therefore, the use of vector quantization in real-time waveform coding systems has been limited to dimension-rate (kr) products of 8 or less. (See "Vector quantization of speech and speech-like waveforms", IEEE Trans. Acoust., Speech, and Sig. Process, H. Abut, R.M. Gray, and G. Rebolledo, ASSP-30, pp. 423-436, Jun. 1982). Thus, although theoretically able to achieve better performance than scalar PCM. due to the complexity problem, vector quantization is not competitive with more sophisticated scalar speech compression methods such as ADPCM, transform coding, or sub-band coding techniques.
Attempts to circumvent the complexity problem are described in the aforementioned Gray and Gersho papers. Alternatives to the optimal yet exhaustive full search of the codebook in vector quantization techniques have been developed in the past few years. However, the majority of these are sub-optimal algorithms which operatate on the original measured vectors (usually in the time domain) in order to reduce complexity.
Therefore, it is desirable to provide an optimal, fast search method for communication systems employing vector quantization systems for speech signal compression, which efficiently reduces computational complexity.